<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="umsroot.css">
<TITLE>
Loop/Iterator Constructs
</TITLE>
</HEAD>
<BODY >
<A HREF="umsroot022.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot021.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="umsroot024.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc49">5.2</A>&nbsp;&nbsp;Loop/Iterator Constructs</H2><UL>
<LI><A HREF="umsroot023.html#toc28">Examples</A>
</UL>

<A NAME="doloops"></A><A NAME="@default154"></A><A NAME="@default155"></A>Many types of simple iterations are inconvenient to write in the
form of recursive predicates. ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> therefore provides a logical
iteration construct
<A HREF="../bips/kernel/control/do-2.html"><B>do/2</B></A><A NAME="@default156"></A>,
which can be understood either by itself
or by its translation to an equivalent recursion.<BR>
<BR>
A simple example is the traversal of a list
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
main :-
        write_list([1,2,3]).

    write_list([]).
    write_list([X|Xs]) :-
        writeln(X),
        write_list(Xs).
</PRE></BLOCKQUOTE>
which can be written as follows without the need for an auxiliary predicate:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
main :-
        ( foreach(X, [1,2,3]) do
            writeln(X)
        ).
</PRE></BLOCKQUOTE>
This looks very much like a loop in a procedural language. However,
due to the relational nature of logic programming, the same <B>foreach</B>-
construct can be used not only to control iteration over an existing list, 
but also to build a new list during an iteration. For example
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
main :-
        ( foreach(X, [1,2,3]), foreach(Y, Negatives) do
            Y is -X
        ),
        writeln(Negatives).
</PRE></BLOCKQUOTE>
will print [-1, -2, -3].<BR>
<BR>
The general form of a do-loop is
<BLOCKQUOTE CLASS="quote">
( IterationSpecs <B>do</B> Goals )
</BLOCKQUOTE>
and it corresponds to a call to an auxiliary recursive
predicate of the form
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
    do__n(...).
    do__n(...) :- Goals, do__n(...).
</PRE></BLOCKQUOTE>
The IterationSpecs determine the number of times the loop is executed
(i.e. the termination condition), and the way information is passed
into the loop, from one iteration to the next, and out of the loop.<BR>
<BR>
IterationSpecs is one (or a comma-separated sequence) of the following:
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>fromto(First,In,Out,Last)</B><DD CLASS="dd-description"><BR>
<A NAME="@default157"></A>iterate Goals starting with In=First until Out=Last.
 In and Out are local variables in Goals. For all but the first
 iteration, the value of In is the same as the value of Out in the
 previous iteration.<BR>
<BR>
<DT CLASS="dt-description"><B>foreach(X,List)</B><DD CLASS="dd-description"><BR>
<A NAME="@default158"></A>iterate Goals with X ranging over all elements of List.
 X is a local variable in Goals.
 Can also be used for constructing a list.<BR>
<BR>
<DT CLASS="dt-description"><B>foreacharg(X,Struct)</B><DD CLASS="dd-description"><BR>
<A NAME="@default159"></A>iterate Goals with X ranging over all elements of Struct.
 X is a local variable in Goals.
 Cannot be used for constructing a term.<BR>
<BR>
<DT CLASS="dt-description"><B>foreacharg(X,Struct,Idx)</B><DD CLASS="dd-description"><BR>
same as before, but Idx is set to the argument position of X in Struct,
 i.e. <CODE>arg(Idx, Struct, X)</CODE> is true.
 Idx is a local variable in Goals.<BR>
<BR>
<DT CLASS="dt-description"><B>foreachelem(X,Array)</B><DD CLASS="dd-description"><BR>
<A NAME="@default160"></A>like foreacharg/2, but iterates over all elements of an array
 of arbitrary dimension. The order is the natural order, i.e.
 if <CODE>Array = []([](a, b, c), [](d, e, f))</CODE>, then for successive
 iterations X is bound in turn to a, b, c, d, e and f.
 X is a local variable in Goals.
 Cannot be used for constructing a term.<BR>
<BR>
<DT CLASS="dt-description"><B>foreachelem(X,Array,Idx)</B><DD CLASS="dd-description"><BR>
same as before, but Idx is set to the index position of X in
 Array, i.e. <CODE>subscript(Array, Idx, X)</CODE> is true.
 Idx is a local variable in Goals.<BR>
<BR>
<DT CLASS="dt-description"><B>foreachindex(Idx,Array)</B><DD CLASS="dd-description"><BR>
<A NAME="@default161"></A>like foreachelem/3, but returns just the index position and not the
 element.<BR>
<BR>
<DT CLASS="dt-description"><B>for(I,MinExpr,MaxExpr)</B><DD CLASS="dd-description"><BR>
<A NAME="@default162"></A>iterate Goals with I ranging over integers from MinExpr to MaxExpr.
 I is a local variable in Goals.
 MinExpr and MaxExpr can be arithmetic expressions.
 Can be used only for controlling iteration, i.e. MaxExpr cannot
 be uninstantiated.<BR>
<BR>
<DT CLASS="dt-description"><B>for(I,MinExpr,MaxExpr,Increment)</B><DD CLASS="dd-description"><BR>
same as before, but Increment can be specified (it defaults to 1).<BR>
<BR>
<DT CLASS="dt-description"><B>multifor(List,MinList,MaxList)</B><DD CLASS="dd-description"><BR>
<A NAME="@default163"></A>like for/3, but allows iteration over multiple indices (saves
 writing nested loops). Each element of List takes a value
 between the corresponding elements in MinList and MaxList.
 Successive iterations go through the possible combinations of
 values for List in lexicographic order. List is a local
 variable in Goals. MinList and MaxList must be either lists of
 arithmetic expressions evaluating to integers, or arithmetic
 expressions evaluating to integers (in the latter case they are
 treated as lists containing the (evaluated) integer repeated an
 appropriate number of times). At least one of List, MinList and
 MaxList must be a list of fixed length at call time so that it is
 known how many indices are to be iterated.<BR>
<BR>
<DT CLASS="dt-description"><B>multifor(List,MinList,MaxList,IncrementList)</B><DD CLASS="dd-description"><BR>
same as before, but IncrementList can be specified (i.e. how
 much to increment each element of List by). IncrementList must be
 either a list of arithmetic expressions evaluating to non-zero
 integers, or an arithmetic expression evaluating to a non-zero
 integer (in which case all elements are incremented by this
 amount). IncrementList defaults to 1.<BR>
<BR>
<DT CLASS="dt-description"><B>count(I,Min,Max)</B><DD CLASS="dd-description"><BR>
<A NAME="@default164"></A>iterate Goals with I ranging over integers from Min up to Max.
 I is a local variable in Goals.
 Can be used for controlling iteration as well as counting,
 i.e. Max can be a variable.<BR>
<BR>
<DT CLASS="dt-description"><B>param(Var1,Var2,...)</B><DD CLASS="dd-description"><BR>
<A NAME="@default165"></A>for declaring variables in Goals global, ie shared with the context.
 CAUTION: By default, variables in Goals are local!
</DL>
Note that fromto/4 is the most general specifier (subsuming the
functionality of all the others), but foreach/2, foreacharg/2,3,
foreachelem/2,3, foreachindex/2, count/3, for/3,4, multifor/3,4 and
param/N are convenient shorthands.<BR>
<BR>
There are three ways to combine the above specifiers in a single do loop:
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>IterSpec1, IterSpec2</B><DD CLASS="dd-description"> (&#8220;synchronous iteration&#8221;)<BR>
<A NAME="@default166"></A>This is the normal way to combine iteration specifiers: simply
 provide a comma-separated sequence of them. The specifiers are
 iterated synchronously; that is, they all take their first
 &#8220;value&#8221; for the first execution of Goals, their second &#8220;value&#8221;
 for the second execution of Goals, etc. The order in which they
 are written does not matter, and the set of local variables in
 Goals is the union of those of IterSpec1 and IterSpec2.<BR>
<BR>
When multiple iteration specifiers are given in this way,
 typically not all of them will impose a termination condition on
 the loop (e.g. <B>foreach</B> with an uninstantiated list and <B>count</B> with an uninstantiated maximum do not impose a termination
 condition), but at least one of them should do so. If several
 specifiers impose termination conditions, then these conditions
 must coincide, i.e. specify the same number of iterations.<BR>
<BR>
<DT CLASS="dt-description"><B>IterSpec1 * IterSpec2</B><DD CLASS="dd-description"> (&#8220;cross product&#8221;)<BR>
<A NAME="@default167"></A>This iterates over the cross product of IterSpec1 and IterSpec2.
 The sequence of iteration is to iterate IterSpec2 completely for a
 given &#8220;value&#8221; of IterSpec1 before doing the same with the next
 &#8220;value&#8221; of IterSpec1, and so on. The set of local variables in
 Goals is the union of those of IterSpec1 and IterSpec2.<BR>
<BR>
<DT CLASS="dt-description"><B>IterSpec1 &gt;&gt; IterSpec2</B><DD CLASS="dd-description"> (&#8220;nested iteration&#8221;)<BR>
<A NAME="@default168"></A>Like ( IterSpec1 do ( IterSpec2 do Goals ) ), including with
 respect to scoping. The local variables in Goals are those of
 IterSpec2; in particular, those of IterSpec1 are not available
 unless IterSpec2 passes them through, e.g. using a <B>param</B>.
 Similarly, the only &#8220;external&#8221; variables available as inputs to
 IterSpec2 are the locals of IterSpec1; variables from outside the
 loop are not available unless passed through by IterSpec1, e.g.
 using a <B>param</B>.
</DL>
Syntactically, the do-operator binds like the semicolon, i.e. less than comma.
That means that the whole do-construct should always be enclosed in
parentheses (see examples).<BR>
<BR>
Unless you use :-pragma(noexpand) or :-dbgcomp, the do-construct is
compiled into an efficient auxiliary predicate named do__nnn, where
nnn is a unique integer. This will be visible during debugging.
To make debugging easier, it is possible to give the loop a
user-defined name by adding <B>loop_name(Name)</B>
<A NAME="@default169"></A>
to the iteration specifiers. Name must be an atom, and is used as the
name of the auxiliary predicate into which the loop is compiled
(instead of do__nnn). The name should therefore not clash with other
predicate names in the same module.<BR>
<BR>
<A NAME="toc28"></A>
<H3 CLASS="subsection"><A NAME="htoc50">5.2.1</A>&nbsp;&nbsp;Examples</H3>
Iterate over list
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
foreach(X,[1,2,3]) do writeln(X).
</PRE></BLOCKQUOTE>
Maplist (construct a new list from an existing list)
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreach(X,[1,2,3]), foreach(Y,List) do Y is X+3).
</PRE></BLOCKQUOTE>
Sumlist
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreach(X,[1,2,3]), fromto(0,In,Out,Sum) do Out is In+X).
</PRE></BLOCKQUOTE>
Reverse list
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreach(X,[1,2,3]), fromto([],In,Out,   Rev) do Out=[X|In]). % or:
(foreach(X,[1,2,3]), fromto([],In,[X|In],Rev) do true).
</PRE></BLOCKQUOTE>
Iterate over integers from 1 up to 5
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
for(I,1,5) do writeln(I). % or:
count(I,1,5) do writeln(I).
</PRE></BLOCKQUOTE>
Iterate over integers from 5 down to 1
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(for(I,5,1,-1) do writeln(I)).
</PRE></BLOCKQUOTE>
Make list of integers [1,2,3,4,5]
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(for(I,1,5), foreach(I,List) do true). % or:
(count(I,1,5), foreach(I,List) do true).
</PRE></BLOCKQUOTE>
Make a list of length 3
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreach(_,List), for(_,1,3) do true). % or:
(foreach(_,List), count(_,1,3) do true).
</PRE></BLOCKQUOTE>
Get the length of a list
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreach(_,[a,b,c]), count(_,1,N) do true).
</PRE></BLOCKQUOTE>
Actually, the length/2 builtin is (almost)
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
length(List, N) :- (foreach(_,List), count(_,1,N) do true).
</PRE></BLOCKQUOTE>
Iterate [I,J] over [1,1], [1,2], [1,3], [2,1], ..., [3,3]:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(multifor([I,J],1,3) do writeln([I,J])).
</PRE></BLOCKQUOTE>
Similar, but have different start/stop values for I and J:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(multifor([I,J], [2,1], [4,5]) do writeln([I,J])).
</PRE></BLOCKQUOTE>
Similar, but only do odd values for the second variable:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(multifor(List, [2,1], [4,5], [1,2]) do writeln(List)).
</PRE></BLOCKQUOTE>
Filter list elements
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreach(X,[5,3,8,1,4,6]), fromto(List,Out,In,[]) do
    X&gt;3 -&gt; Out=[X|In] ; Out=In).
</PRE></BLOCKQUOTE>
Iterate over structure arguments
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreacharg(X,s(a,b,c,d,e)) do writeln(X)).
</PRE></BLOCKQUOTE>
Collect args in list
(bad example, use =.. if you really want to do that!)
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreacharg(X,s(a,b,c,d,e)), foreach(X,List) do true).
</PRE></BLOCKQUOTE>
Collect args reverse
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreacharg(X,s(a,b,c,d,e)), fromto([],In,[X|In],List) do true).
</PRE></BLOCKQUOTE>
or like this:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
S = s(a,b,c,d,e), functor(S, _, N),
(for(I,N,1,-1), foreach(A,List), param(S) do arg(I,S,A)).
</PRE></BLOCKQUOTE>
Rotate args in a struct
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
S0 = s(a,b,c,d,e), functor(S0, F, N), functor(S1, F, N),
(foreacharg(X,S0,I), param(S1, N) do I1 is (I mod N)+1, arg(I1,S1,X)).
</PRE></BLOCKQUOTE>
Flatten an array into a list
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(foreachelem(X,[]([](5,1,2),[](3,3,2))), foreach(X,List) do true).
</PRE></BLOCKQUOTE>
Transpose a 2D array
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
A = []([](5,1,2),[](3,3,2)), dim(A, [R,C]), dim(T, [C,R]),
(foreachelem(X,A,[I,J]), param(T) do X is T[J,I]).
</PRE></BLOCKQUOTE>
Same, using foreachindex
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
A = []([](5,1,2),[](3,3,2)), dim(A, [R,C]), dim(T, [C,R]),
(foreachindex([I,J],A), param(A, T) do
    subscript(A, [I,J], X), subscript(T, [J,I], X)).
</PRE></BLOCKQUOTE>
The following two are equivalent
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
foreach(X,[1,2,3])        do             writeln(X).
fromto([1,2,3],In,Out,[]) do In=[X|Out], writeln(X).
</PRE></BLOCKQUOTE>
The following two are equivalent
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
count(I,1,5)     do            writeln(I).
fromto(0,I0,I,5) do I is I0+1, writeln(I).
</PRE></BLOCKQUOTE>
Some examples for nested loops. Print all pairs of list elements:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
Xs = [1,2,3,4],
( foreach(X, Xs), param(Xs) do
    ( foreach(Y,Xs), param(X) do
        writeln(X-Y)
    )
).
% or
Xs = [1,2,3,4],
( foreach(X, Xs) * foreach(Y, Xs) do
    writeln(X-Y)
).
</PRE></BLOCKQUOTE>
and the same without symmetries:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
Xs = [1,2,3,4],
( fromto(Xs, [X|Xs1], Xs1, []) do
    ( foreach(Y,Xs1), param(X) do
        writeln(X-Y)
    )
).
% or
Xs = [1,2,3,4],
( fromto(Xs, [X|Xs1], Xs1, []) &gt;&gt; ( foreach(Y,Xs1), param(X) ) do
    writeln(X-Y)
).
</PRE></BLOCKQUOTE>
Find all pairs of list elements and collect them in a result list:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
pairs(Xs, Ys, Zs) :-
    (
        foreach(X,Xs),
        fromto(Zs, Zs4, Zs1, []),
        param(Ys)
    do
        (
            foreach(Y,Ys),
            fromto(Zs4, Zs3, Zs2, Zs1),
            param(X)
        do
            Zs3 = [X-Y|Zs2]
        )
    ).
% or
pairs(Xs, Ys, Zs) :-
    (
        foreach(X, Xs) * foreach(Y, Ys),
        foreach(Z, Zs)
    do
        Z = X-Y
    ).
</PRE></BLOCKQUOTE>
Flatten a 2-dimensional matrix into a list:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
flatten_matrix(Mat, Xs) :-
    dim(Mat, [M,N]),
    (
        for(I,1,M),
        fromto(Xs, Xs4, Xs1, []),
        param(Mat,N)
    do
        (
            for(J,1,N),
            fromto(Xs4, [X|Xs2], Xs2, Xs1),
            param(Mat,I)
        do
            subscript(Mat, [I,J], X)
        )
    ).
</PRE></BLOCKQUOTE>
Same using * to avoid nesting:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
flatten_matrix(Mat, Xs) :-
    dim(Mat, [M,N]),
    (
        for(I, 1, M) * for(J, 1, N),
        foreach(X, Xs),
        param(Mat)
    do
        subscript(Mat, [I,J], X)
    ).
</PRE></BLOCKQUOTE>
Same using multifor to avoid nesting:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
flatten_matrix(Mat, Xs) :-
    dim(Mat, [M,N]),
    (
        multifor([I,J], 1, [M,N]),
        foreach(X, Xs),
        param(Mat)
    do
        subscript(Mat, [I,J], X)
    ).
</PRE></BLOCKQUOTE>
Same for an array of arbitrary dimension:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
flatten_array(Array, Xs) :-
    dim(Array, Dims),
    (
        multifor(Idx, 1, Dims),
        foreach(X, Xs),
        param(Array)
    do
        subscript(Array, Idx, X)
    ).
</PRE></BLOCKQUOTE>
Same but returns the elements in the reverse order:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
flatten_array(Array, Xs) :-
    dim(Array, Dims),
    (
        multifor(Idx, Dims, 1, -1),
        foreach(X, Xs),
        param(Array)
    do
        subscript(Array, Idx, X)
    ).
</PRE></BLOCKQUOTE>
Flatten nested lists one level (cf. flatten/2 which flattens completely):
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
List = [[a,b],[[c,d,e],[f]],[g]],
(foreach(Xs,List) &gt;&gt; foreach(X,Xs), foreach(X,Ys) do true).
</PRE></BLOCKQUOTE>
Iterate over all ordered pairs of integers 1..4 (param(I) required to make
I available in body of loop):
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
(for(I,1,4) &gt;&gt; (for(J,I+1,4), param(I)) do writeln(I-J)).
</PRE></BLOCKQUOTE>
Same for general 1..N (param(N) required to make N available to second for):
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
N=4,
((for(I,1,N), param(N)) &gt;&gt; (for(J,I+1,N), param(I)) do writeln(I-J)).
</PRE></BLOCKQUOTE>
<HR>
<A HREF="umsroot022.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot021.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="umsroot024.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
